package leetcode;

import java.util.Arrays;

public class MaximumGap {

	public static void main(String[] args) {
		MaximumGap gap = new MaximumGap();
//		int[] nums = {15252,16764,27963,7817,26155,20757,3478,22602,20404,6739,16790,10588,16521,6644,20880,15632,
//		               27078,25463,20124,15728,30042,16604,17223,4388,
//		               23646,32683,23688,12439,30630,3895,7926,22101,32406,21540,31799,3768,26679,21799,23740};
		int[] nums = {1, 1000000};
		gap.maximumGap(nums);
		String string = "\\\\(";
		System.out.println(string);
	}
	
//	Suppose there are N elements in the array, the min value is min and the max value is max. 
//	Then the maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)].

	//variable gap means average gap;	
//	Let gap = ceiling[(max - min ) / (N - 1)]. We divide all numbers in the array into n - 1 buckets
//	where k-th bucket contains all numbers in [min + (k-1)gap, min + k * gap) 
//	i.e. : the first bucket contains: [min, min + gap)
	
//	Since there are most n - 2 numbers that are not equal min or max and there are n-1 buckets
//	at least one of the buckets are empty
	
//	We only need to store the largest number and the smallest number in each bucket.

//	After we put all the numbers into the buckets. We can scan the buckets sequentially and get the max gap.
	public int maximumGap(int[] nums) {
		if (nums == null || nums.length <= 1) {
			return 0;
		}
		int max = nums[0];
		int min = nums[0];
		for (int i : nums) {
			min = Math.min(min, i);
			max = Math.max(max, i);
		}
 		if(min == max){
		    return 0;
		}
		//n个元素的平均距离为：(max - min) / (n - 1)
		//但是有个问题是max 可能等于min,所以(max - min) / (nums.length - 1) + 1
		//这样gap最小为1
		int gap = (max - min - 1) / (nums.length - 1) + 1;
		int bucketNum = (max - min) / gap + 1;
		
		int[] bucketsMin = new int[bucketNum];
		int[] bucketsMax = new int[bucketNum];
		Arrays.fill(bucketsMin, Integer.MAX_VALUE);
		Arrays.fill(bucketsMax, Integer.MIN_VALUE);
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != max && nums[i] != min) {
				int buckInd = (nums[i] - min) / gap ;
				bucketsMin[buckInd] = Math.min(bucketsMin[buckInd], nums[i]);
				bucketsMax[buckInd] = Math.max(bucketsMax[buckInd], nums[i]);
			}
		}
		int maxGap = Integer.MIN_VALUE;
		int previous = min;
		for (int i = 0; i < bucketNum; i++) {
			if (bucketsMin[i] == Integer.MAX_VALUE
					&& bucketsMax[i] == Integer.MIN_VALUE) {
				// is a empty bucket
				continue; 
			}
			// i_th gap is minvalue in i + 1_th bucket minus maxvalue in i_th bucket
			maxGap = Math.max(maxGap, bucketsMin[i] - previous);
			previous = bucketsMax[i];
		}
		// updata the final max value gap, for example, there are only two numbers 
		maxGap = Math.max(maxGap, max - previous);
		return maxGap;
	}
}
